# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not list1:
            return list2
        if not list2:
            return list1
        lp1 = list1
        lp2 = list2
        if lp1.val < lp2.val:
            hp = lp1
            lp1 = lp1.next
        else:
            hp = lp2
            lp2 = lp2.next
        tp = hp
        while lp1 and lp2:
            if lp1.val < lp2.val:
                tp.next = lp1
                tp = lp1
                lp1 = lp1.next
            else:
                tp.next = lp2
                tp = lp2
                lp2 = lp2.next
        if lp1:
            tp.next = lp1
        if lp2:
            tp.next = lp2
        return hp
